package com.leetcode.专项突破.排序算法全解析;

import com.leetcode.common.utils.ArrayUtils;
import java.util.Arrays;
import java.util.function.BiFunction;

/**
 * @author 覃国强
 * @date 2022-05-11 16:46
 */
public class B01_堆排序 {

  public static void main(String[] args) {
    HeapSort heapSort = new HeapSort();
    int[] arr = ArrayUtils.randomArr(20);
    System.out.println("origin: " + Arrays.toString(arr));
    heapSort.sort(arr);
    System.out.println("sorted: " + Arrays.toString(arr));
  }


  static class HeapSort {

    public void sort(int[] arr) {
      BiFunction<Integer, Integer, Boolean> predicate = (target, candidate) -> target < candidate;
      buildHeap(arr, predicate);
      for (int i = arr.length - 1; i > 0; --i) {
        swap(arr, 0, i);
        heapify(arr, 0, i, predicate);
      }
    }

    private void buildHeap(int[] arr, BiFunction<Integer, Integer, Boolean> predicate) {
      for (int i = (arr.length - 2) / 2; i >= 0; --i) {
        heapify(arr, i, arr.length, predicate);
      }
    }

    private void heapify(int[] arr, int i, int size, BiFunction<Integer, Integer, Boolean> predicate) {
      int left = 2 * i + 1;
      int right = 2 * i + 2;
      int target = i;
      if (left < size && predicate.apply(arr[target], arr[left])) {
        target = left;
      }
      if (right < size && predicate.apply(arr[target], arr[right])) {
        target = right;
      }
      if (target != i) {
        swap(arr, i, target);
        heapify(arr, target, size, predicate);
      }
    }

    private void swap(int[] arr, int i, int j) {
      int temp = arr[i];
      arr[i] = arr[j];
      arr[j] = temp;
    }
  }

}
